package com.wtgroup.demo.mianshi.算法.动态规划.数字转字母;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 60906
 * @date 2021/5/12 17:00
 */
public class D {
    /*
    * 1-A, 2-B, 3-C ...
    * 111 -> AAA or KA or AK
    *
    * */

    @Test
    public void foo1() {
        String str = "111";
        List<String> res = new Solution_Rec().run(str);
        System.out.println(res);
    }

    /**
     * 暴力递归
     * 回溯
     */
    class Solution_Rec {

        public List<String> run(String str) {
            List<String> vessel = new ArrayList<>();
            StringBuilder path = new StringBuilder();
            func(str, 0, path, vessel);
            return vessel;
        }

        void func(String str, int start, StringBuilder path, List<String> vessel) {
            if (start==str.length()) {
                vessel.add(path.toString());
                /*
                * 需要返回转换方案个数时, 这里 return 1. 为什么不是 return 0 呢? 到这里说明前面的转换方案定了, 收集一个.
                * 相当于数值容器收集一个数.
                * */
                return;
            }

            int curr = 0;
            for (int i = start; i < str.length(); i++) {
                curr = curr * 10 + (str.charAt(i)-'0');
                if (curr > 26) {
                    continue;
                }
                path.append((char)(curr-1 + 'A'));
                func(str, i + 1, path, vessel);
                path.deleteCharAt(path.length() - 1);
            }

        }

    }

}
